//
// Created by LiuYou on 2021/12/2.
//

#include <iostream>
#include <vector>
#include <iterator>


/*
 * 某个数现在在 index位置。
 *
 * 这个函数的功能是: 将 index位置 上的值加入到堆(大顶堆)中, 然后维持一个大顶堆。
 */
static void heapInsert(std::vector<int>& arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        std::swap( arr[index], arr[(index - 1) / 2] );

        // 然后将这个值的下标与之前的父结点的下标交换, 然后进入while判断条件
        // 判断这个值是否还是比父结点大。
        // 如果比父结点大, 还交换; 如果不如父结点大, 那么就维持好了一个大顶堆。
        index = (index - 1) / 2;
    }
}


static void heapify(std::vector<int>& arr, int index, int heapSize) {
    // left: leftChildIndex
    int left = index * 2 + 1;
    while (left < heapSize) {
        int largest{};
        if (left + 1 < heapSize && arr[left + 1] > arr[left]) {
            largest = left + 1;
        } else {
            largest = left;
        }

        if (arr[largest] > arr[index]) { ;
        } else {
            largest = index;
        }

        if (largest == index) {
            break;
        } else {
            std::swap( arr[largest], arr[index] );
            index = largest;
            left = index * 2 + 1;
        }
    }
}


static void heapSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // 将这个数组构建为大顶堆的数据结构。
    for (int i = 0; i < arr.size(); ++i) {
        heapInsert( arr, i );
    }
    int heapSize = arr.size();

    // 然后通过不断的交换大顶堆的第一个元素与最后一个元素,
    // 此时最后一个元素一定是最大的, 然后这个数组就排好序。
    std::swap( arr[0], arr[--heapSize] );
    // 将第一个元素与最后一个元素交换后, 就不是大顶堆了, 需要调整, 而且大顶堆的大小也 - 1。
    while (heapSize > 0) {
        // 调整大顶堆。
        // 调整的数组范围是 [0, heapSize), 即 [0, heapSize - 1]。
        heapify( arr, 0, heapSize );
        std::swap( arr[0], arr[--heapSize] );
    }

}


int main(int argc, char** argv) {
    std::vector<int> arr{5, 1, 2, 4, 3, 9, 8};
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;

    heapSort( arr );

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}
